147. 对链表进行插入排序

function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

var insertionSortList = function(head) {
  if (head === null) return head;

  const dummyHead = new ListNode(0); // 为了便于在 head 节点之前插入节点
  dummyHead.next = head;
  let last = head, // 为链表的已排序部分的最后一个节点
    curr = head.next; //  为待插入的元素

  while (curr !== null) {
    if (last.val <= curr.val) {
      last = last.next;
    } else {
      let prev = dummyHead;
      while (prev.next.val <= curr.val) {
        prev = prev.next; // 为插入 curr 的位置的前一个节点
      }
      last.next = curr.next; // 缓存已排序部分后的待插入元素
      curr.next = prev.next; // 缓存插入的节点
      prev.next = curr; // 插入节点
    }

    curr = last.next; // 更新待插入节点
  }

  return dummyHead.next;
};
console.log(
  insertionSortList({
    val: 4,
    next: {
      val: 2,
      next: {
        val: 1,
        next: {
          val: 3,
          next: null,
        },
      },
    },
  })
);